#ifndef _math_pow_h_
#define _math_pow_h_

#include<contest/bigint.h>

namespace contest
{
/**
 * Power function by binary exponentiation. It grants no overflow.
 * @param base: The number to be raised.
 * @param exp: The exponent.
 * @param mod: The modulo of the exponent.
 **/
template <class A> 
uint64_t powmod(const A base, const uint64_t exp, const uint64_t mod)
{
    if (exp == 0)
        return 1 % mod;
    if (exp == 1)
        return base % mod;
    uint64_t half = powmod(base, (exp>>1), mod);
    bigint full = half;
    full *= half;
    if (exp % 2 == 0)
        return full % mod;
    return (full * base) % mod;
}
}

#endif
